Rigid body dynamics is widely used in applications ranging from movies to engineering to video games. Piles of objects are particularly common, because ultimately, gravity pulls all rigid bodies to the ground. Some of the most visually interesting simulations involve destruction, such as projectile impacts and explosions, and these can generate large piles of debris. In mechanical engineering some of the most computationally challenging problems involve simulating interaction with large resting systems of soil particles or rocks. Piles require stable simulation of static friction, dynamic friction and resting contact, which present many challenges.
In large-scale or real-time simulations, the time available for computation can be small compared to the number of rigid body contacts. In these cases iterative methods are used to solve rigid body dynamics. However, iteration is often terminated well before convergence to maximize the rigid body count. This results in residual energy, which can cause artifacts when its distribution over the contacts varies too much from frame to frame. The effect of this can be seen when bodies coming to rest oscillate (jitter) or move around each other non-physically (swim).
A commonly used iterative algorithm for simulating interactions is serial projected Gauss-Seidel (PGS), which solves contacts in sequence. When the iteration is terminated, the last contact solved has no error and the other contacts have non-zero error, resulting in an uneven distribution of the residual energy. On single threaded implementations the distribution of this error can be made consistent from frame to frame by, for example, by ensuring that collisions are detected in the same order each frame and that addition and deletion of bodies do not disrupt the order.
Unfortunately, things are not as straightforward for parallel implementations. PGS has limited parallelism, as updates to bodies having multiple contacts must be serialized to ensure they are not lost and the connectivity between bodies can be complex, especially in piles. It is very challenging to avoid jittering and swimming with parallel PGS, and due to serialization its performance does not scale well as more threads are added.